using System.Collections.Generic;

namespace GGPhysics
{
	public class GGLinkedList<T>
	{
		protected GGLinkedListNode<T> firstNode;

		protected GGLinkedListNode<T> lastNode;

		protected int count;

		protected GGLinkedListNode<T> lastBufferedNode;

		public int sortIterations;

		public GGLinkedListNode<T> First
		{
			get
			{
				return firstNode;
			}
		}

		public GGLinkedListNode<T> Last
		{
			get
			{
				return lastNode;
			}
		}

		public int Count
		{
			get
			{
				return count;
			}
		}

		public GGLinkedListNode<T> Buffer
		{
			get
			{
				return lastBufferedNode;
			}
		}

		public void AddLast(T val)
		{
			GGLinkedListNode<T> node = GetNode(val);
			AddNodeToEnd(ref lastNode, node);
			if (node.Previous == null)
			{
				firstNode = node;
			}
			count++;
		}

		public void AddFirst(T val)
		{
			GGLinkedListNode<T> node = GetNode(val);
			AddNodeToStart(ref firstNode, node);
			if (node.Next == null)
			{
				lastNode = node;
			}
			count++;
		}

		public GGLinkedListNode<T> RemoveAndDetachNode(GGLinkedListNode<T> node)
		{
			if (node.Previous != null)
			{
				node.Previous.Next = node.Next;
			}
			if (node.Next != null)
			{
				node.Next.Previous = node.Previous;
			}
			if (firstNode == node)
			{
				firstNode = node.Next;
			}
			if (lastNode == node)
			{
				lastNode = node.Previous;
			}
			count--;
			return node;
		}

		public void Remove(GGLinkedListNode<T> node)
		{
			RemoveAndDetachNode(node);
			AddNodeToEnd(ref lastBufferedNode, node);
		}

		public void Clear()
		{
			GGLinkedListNode<T> next = firstNode;
			while (next != null)
			{
				GGLinkedListNode<T> gGLinkedListNode = next;
				next = gGLinkedListNode.Next;
				AddNodeToEnd(ref lastBufferedNode, gGLinkedListNode);
			}
			count = 0;
			firstNode = (lastNode = null);
		}

		protected void AddNodeToEnd(ref GGLinkedListNode<T> lastNode, GGLinkedListNode<T> newNode)
		{
			newNode.Previous = lastNode;
			newNode.Next = null;
			if (lastNode != null)
			{
				lastNode.Next = newNode;
			}
			lastNode = newNode;
		}

		protected void AddNodeToStart(ref GGLinkedListNode<T> firstNode, GGLinkedListNode<T> newNode)
		{
			newNode.Previous = null;
			newNode.Next = firstNode;
			if (firstNode != null)
			{
				firstNode.Previous = newNode;
			}
			firstNode = newNode;
		}

		protected GGLinkedListNode<T> GetNode(T val)
		{
			GGLinkedListNode<T> gGLinkedListNode = null;
			if (lastBufferedNode != null)
			{
				gGLinkedListNode = lastBufferedNode;
				lastBufferedNode = lastBufferedNode.Previous;
				if (lastBufferedNode != null)
				{
					lastBufferedNode.Next = null;
				}
			}
			else
			{
				gGLinkedListNode = new GGLinkedListNode<T>();
			}
			gGLinkedListNode.Value = val;
			return gGLinkedListNode;
		}

		private void SwapValue(GGLinkedListNode<T> l, GGLinkedListNode<T> h)
		{
			T value = l.Value;
			l.Value = h.Value;
			h.Value = value;
		}

		private GGLinkedListNode<T> Partition(GGLinkedListNode<T> l, GGLinkedListNode<T> h, IComparer<T> comparer)
		{
			T value = h.Value;
			GGLinkedListNode<T> gGLinkedListNode = l.Previous;
			sortIterations++;
			for (GGLinkedListNode<T> gGLinkedListNode2 = l; gGLinkedListNode2 != h; gGLinkedListNode2 = gGLinkedListNode2.Next)
			{
				sortIterations++;
				if (comparer.Compare(gGLinkedListNode2.Value, value) <= 0)
				{
					gGLinkedListNode = ((gGLinkedListNode != null) ? gGLinkedListNode.Next : l);
					SwapValue(gGLinkedListNode, gGLinkedListNode2);
				}
			}
			gGLinkedListNode = ((gGLinkedListNode != null) ? gGLinkedListNode.Next : l);
			SwapValue(gGLinkedListNode, h);
			return gGLinkedListNode;
		}

		protected void QuickSort(GGLinkedListNode<T> l, GGLinkedListNode<T> h, IComparer<T> comparer)
		{
			if (h != null && l != h && l != h.Next)
			{
				GGLinkedListNode<T> gGLinkedListNode = Partition(l, h, comparer);
				QuickSort(l, gGLinkedListNode.Previous, comparer);
				QuickSort(gGLinkedListNode.Next, h, comparer);
			}
		}

		public void QuickSort(IComparer<T> comparer)
		{
			sortIterations = 0;
			QuickSort(firstNode, lastNode, comparer);
		}

		public void InsertionSort(IComparer<T> comparer)
		{
			GGLinkedListNode<T> next = firstNode;
			if (next == null)
			{
				return;
			}
			sortIterations = 0;
			while (next != null)
			{
				GGLinkedListNode<T> gGLinkedListNode = next;
				next = next.Next;
				GGLinkedListNode<T> previous = gGLinkedListNode.Previous;
				while (previous != null && comparer.Compare(previous.Value, previous.Next.Value) > 0)
				{
					SwapValue(previous, previous.Next);
					previous = previous.Previous;
					sortIterations++;
				}
				sortIterations++;
			}
		}
	}
}
